# -*- coding: utf-8 -*-
# @Author: shj
# @Date: 2020-04-10 18:47:54
# @LastEditTime: 2020-04-10 19:48:44
# @LastEditors: shj
# @Description: 动态规划例子：子列表元素之和的最大值。
# @FilePath: /python3/algorithms/Dynamic_programing.py
'''
动态规划 - 基本思想同分治法相似也是将待求解问题分解成若干个子问题，
先求解并保存这些子问题的解，避免产生大量的重复运算。

说明：子列表指的是列表中索引（下标）连续的元素构成的列表；
列表中的元素是int类型，可能包含正整数、0、负整数；
程序输入列表中的元素，输出子列表元素求和的最大值，例如：
输入：1 -2 3 5 -3 2
输出：8
输入：0 -2 3 5 -1 2
输出：9
输入：-9 -2 -3 -5 -3
输出：-2

说明：这个题目最容易想到的解法是使用二重循环，但是代码的时间性能将会变得非常的糟糕。
使用动态规划的思想，仅仅是多用了两个变量，就将原来O(N2)复杂度的问题变成了O(N)。
'''


def son_sum():
    '''计算子序列（下标连续）和的最大值'''
    # 完整序列
    items = list(map(int, input("请输入一串整数数列（eg: 0, 1, -2 3），用空格分隔：\n").split()))
    # 最终和    局部和    初值为第一个元素
    overall = partial = items[0]
    for i in range(1, len(items)):  # 对序列取和
        # 比较当前元素与局部和，取二者中大的作为新的局部和
        partial = max(items[i], partial + items[i])
        # 比较计算后的局部和与初始的最终和，二者中取较大者
        overall = max(partial, overall)
    print(f'子序列和的最大值为: {overall}')


if __name__ == "__main__":
    son_sum()